package src.week11.SHIYAN7.Demo3;

public class Searching2
{

    // 1 7 11 9 23
    public static boolean linearSearch(double[] seed, double obj)
    {
        int i;
        double[] a = new double[100];
        a[0] = obj;//设置哨兵

        for (i = 1; i <=seed.length; i++) {
            a[i] = seed[i - 1];
        }

        while (a[i]!= obj)
        {
            i--;
        }

        if (i == 0)
            return false;
        else
            return true;
    }
    public static Comparable BinarySearch (Comparable[] data, Comparable target)
    {
        Comparable result = null;
        int first = 0, last = data.length-1, mid;
        while (result == null && first <= last)
        {
            mid = (first + last) / 2;  // determine midpoint
            if (data[mid].compareTo(target) == 0)
                result = data[mid];
            else
            if (data[mid].compareTo(target) > 0)
                last = mid - 1;
            else
                first = mid + 1;
        }

        return result;

    }

    //插值查找

    public static boolean InsertSearch(int[] a, int value, int low, int high) {

        int mid = low + (value - a[low]) / (a[high] - a[low]) * (high - low);
        if (a[mid] == value)
            return true;
        if (a[mid] > value)
            return InsertSearch(a, value, low, mid - 1);
        else
            return InsertSearch(a, value, mid + 1, high);

    }
    public static boolean FibonacciSearch(int[] table, int keyWord) {
        //确定需要的斐波那契数
        int i = 0;
        while (getnFibonacci(i) - 1 == table.length) {
            i++;
        }
        //开始查找
        int low = 0;
        int height = table.length - 1;
        while (low <= height) {
            int mid = low + getnFibonacci(i - 1);
            if (table[mid] == keyWord) {
                return true;
            } else if (table[mid] > keyWord) {
                height = mid - 1;
                i--;
            } else if (table[mid] < keyWord) {
                low = mid + 1;
                i -= 2;
            }
        }
        return false;
    }
    //得到第n个斐波那契数
    public static int getnFibonacci(int n) {
        int ak = 0;
        if (n == 0) {
            ak = 0;
        } else if (n == 1) {
            ak = 1;
        } else {
            int first = 0;
            int second = 1;
            for (int i = 2; i <= n; i++) {
                ak = first + second;
                first = second;
                second = ak;
            }
        }
        return ak;
    }

}